package algorithm_demo.demo04;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/
 *
 * @author Api
 * @date 2023/2/18 15:32
 */
public class Code05_FindUnsortedSubarray {
    /*
    给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
    请你找出符合题意的 最短 子数组，并输出它的长度。
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

    public static void main(String[] args) {
        int[] nums = new int[]{2,6,4,8,10,9,15};
        int unsortedSubarray = findUnsortedSubarray(nums);
        System.out.println(unsortedSubarray);
    }

    public static int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //判断当前nums是否为有序数组
        if (isSort(nums)) {
            return 0;
        }
        int[] help = new int[nums.length];
        System.arraycopy(nums, 0, help, 0, nums.length);
        //help排序
        Arrays.sort(help);
        //左边
        int left = 0;
        while (nums[left] == help[left]) {
            left++;
        }
        //右边
        int right = nums.length - 1;
        while (nums[right] == help[right]) {
            right--;
        }
        return right-left+1;
    }
    public static boolean isSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
}
